COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00006 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A01.Tex[262,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, March 15, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Analysis of Radix Exchange}

Applying radix exchange to $n+1$ records, the chance that the $k+1↑{st}$ bit
of a record is examined is $1-(1-2↑{-k})↑n \sim 1- \exp (- {n\over 2↑k})$.  The
expected number of bit inspections per record is 
$$\displaylines{\phi (n) = \sum↓{k\geq 0}\left (1- \left (1 - 2↑{-k}  
\right )↑n\right) = O\left (1\over h\right ) + f(n),\cr
f(n) = \sum↓{k\geq 0}\left (1-\exp\left (-{n\over 2↑k}\right ) \right ).\cr}$$
Let $x=e↑{-n}$;
$$f(n) = (1-x) + (1-x↑{1/2}) + (1-x↑{1/4}) + \cdots$$
Let $$\eqalign{h(n) & = x↑2+x↑4+x↑8+\cdots = e↑{-2n}+ e↑{-4n}+ e↑{-8n}+\cdots\cr
f(2n) & = 1-x↑2+ f(n)\cr
h(2n) & = h(n) - x↑2\cr}$$
$$[f(n) - \lg n - h(n)] - [f(2n) - \lg(2n) - h(2n)] = 0,$$
so $f(n) - \lg n - h(n) = L(n)$ has period $1$ in $\lg n$.  If $n = 2↑a\nu$,
with $1 \leq \nu < 2 (\hbox {or}\, {1\over 2} \leq\nu < 1)$,
$L(n) = L(\nu)$, so we need tabulate $L$ only for such a range. 

Then $f(n) = \lg n + h(n) + L(n)$,
$$\phi (n) = \lg n + L(n) + O \left ({1\over n}\right ) + h(n),$$
where $L(n) = {\bf 1.3327462} \pm {\bf 0.000001498}$ (see table) is periodic
in $\lg n$; $h(n) \epsilon O\left (e↑{-2n}\right )$ is negligible if
$n \geq 12$, and is superexponentially convergent.

$- L(n)$ can be calculated from $x$ to precision $O(\epsilon)$ by
$$\eqalign{&\left (x+x↑{1/2}+x↑{1/4}+\cdots\right )↓{t\ \rm terms}-t\cr
&\quad + \left (x↑2+x↑4+x↑8+\cdots\right ) + \lg n.\cr}$$
Here the first series stops at a term greater than $1-\epsilon$, using
successive square root operations, and the second stops at a term less than
$\epsilon$, using successive squarings.  For $b$-bit precision, the first
sum needs about $b$ terms; the second needs about $\lg b$ terms.  The sequence
in the first sum can be made more rapidly convergent by successively
applying the operators ${2E-1\over 1}$, ${4E-1\over 3}$, ${8E-1\over 7}$, etc.
\goodbreak
\halign{\qquad#\hfill&\quad#\hfill&#\hfill\cr
\hfill $\nu$&\hfill\hfill $L(\nu)$\hfill\hfill\span\cr
1.0&1.33274 &7389\cr
1.1&1.33274 &7741\cr
1.2&1.33274 &7096\cr
1.3&1.33274 &6015\cr
1.4&1.33274 &5084\cr
1.5&1.33274 &4635\cr
1.6&1.33274 &4746\cr
1.7&1.33274 &5298\cr
1.8&1.33274 &6057\cr
1.9&1.33274 &6809\cr
&&\hrulefill\cr
&&6243 avg\cr}
\bye